﻿using System;
using System.Collections.Generic;

namespace JH
{
    public static class CollectionExtensions
    {
        /// <summary>
        /// 在排序好的 IList 中执行二分查找
        /// </summary>
        /// <typeparam name="T">集合中元素的类型</typeparam>
        /// <param name="list">排序好的集合</param>
        /// <param name="item">要查找的目标值</param>
        /// <param name="comparer">比较器（可选，如果为 null 则使用默认比较器）</param>
        /// <returns>找到目标值的索引，如果未找到，返回插入点的负值（按位取反 ~）</returns>
        /// <exception cref="InvalidOperationException">当集合不是有序的时，行为未定义</exception>
        public static int BinarySearch<T>(this IList<T> list, T item, IComparer<T> comparer = null)
        {
            if (list == null) throw new ArgumentNullException(nameof(list), "集合不能为空");

            // 如果没有提供比较器，则使用默认比较器
            comparer ??= Comparer<T>.Default;
            int left = 0;
            int right = list.Count - 1;

            while (left <= right)
            {
                // 防止溢出
                int mid = left + (right - left) / 2; 
                int comparison = comparer.Compare(list[mid], item);
               
                // 找到目标值，返回索引
                if (comparison == 0) return mid;
               
                // 搜索右半部分
                if (comparison < 0) left = mid + 1;
                
                // 搜索左半部分
                else right = mid - 1;
            }

            // 未找到目标值，返回插入点的负值（按位取反 ~left）
            return ~left;
        }
    }
}